The invention makes use of ordinal value filters, which term is to be interpreted in the light of subsequent comments, and a brief explanation of the art relating to these filters is appropriate before describing the invention. An alternative term for ordinal value filters, sometimes used in relevant literature, is a rank filter.
A real time ordinal value filter which determines which one of a set of R applied data values is the Nth-largest, becomes a median filter if R is odd and N is made equal to (R+1)/2. In such a mode the filter provides as an output the "middle" value of the data set, having in general an equal number of other data values from the set larger and smaller than itself.
The design and operation of median filters is described inter alia in U.S. Pat. Nos. 4,441,165, 4,439,840, 4,560,974 and 45,135,440.
In a simple case of a linear array of data samples, if R=3 and N=2, the median value is the middle value of each three successive data values when the latter are sorted into order, beginning with the smallest and ending with the largest of each group of three. Since there is no averaging the median filter will remove spurious samples without degrading sharp transitions in the original sample series. Put another way, if the data samples represent a regularly sampled, time dependent signal, then the median filter has the property of not restricting the band width of the signal (which would degrade steep transitions in the original signal) but instead allows original signal transitions, representing long duration features, to be transmitted at full band width while substantially attenuating shorter duration spurious spikes, characteristic of electrical noise.
The particular threshold at which such a filter will eliminate spurious signals but pass other signals is determined by the values of R and N. The greater the number of atypical samples that represent the spurious signal that is to be eliminated, the greater will have to be the value of R.
However, it has been found that a median filter, set to eliminate spurious spikes represented by less than N samples for example, may actually introduce spurious signals that are longer than N samples in duration into the filter output, when a succession of short spikes are closer together than N sampling intervals. This can have serious repercussions if the information is contained, at least in part, in the number of samples representing the amplitude excursions in the original.
In an attempt to further enhance noise reduction, it has been proposed to repeat a median filtering step by applying the filtered signal from a first median filter, either to the input of the same filter again or to a second identical filter. If this is repeated until no further changes are introduced by the signal, it is called a root median filter. At first it was thought that this might overcome the introduction of spurious signals as discussed above, but it has been found that this repeated ordinal value filtering does not resolve the problem.
Experiments have shown that the introduction of adventitious information into the filter output is reduced when the value of R is small. For example, in the case of a linear sequence of samples, if R=3, it would appear that there is little likelihood of any spurious additional signals appearing in the output. By appropriate choice of sampling interval, a median filter with a value of R=3 should not introduce any unwanted signal transitions in the filter output signal. However, spurious signals represented by two or more samples will not be suppressed, which, when the sampling rate is high, may not result in very satisfactory noise reduction.
Increasing the number of samples representing a given signal will not necesssarily result in an increase in the accuracy of the filtered signal since the value of R has to be increased to take account of the greater number of sampling intervals which will have occurred during a given spurious noise signal spike.
The present invention, in one aspect, seeks to extend the range of filters that can be serially connected to form a datasieve, for example as described in European Patent No. 0383814 and so overcome this apparently fundamental problem associated with ordinal value filters (and median filters in particular), when they are employed to remove unwanted signals from a signal conglomerate containing broadband wanted signals, i.e. employed as a datasieve.
Thus, the present invention is also concerned with datasieves. Such datasieves are disclosed in the above mentioned European Patent and also in the research paper by J A Bangham reported in IEEE Transactions, Signal Processing vol 41: pp31 to 42 (1993). A brief explanation of these devices, now follows.
A datasieve may consist of a cascade (series) of ordinal (rank order) filters of increasing window size. However, it is to be understood that the ordinal filter at each stage may comprise more than one processing device; for example a filter may comprise one or more median filters, a sequence of max, min, min, max or min, max, max, min filters, or the rank may vary fom one to another of the stages. The terms "ordinal filters" and "rank filters" therefore have to be understood to include combinations of max/min operators, e.g. max/min morphological operators, and it is an aspect of this invention also to include weighted order filters, which have hitherto been used specifically only for noise reduction, and furthermore "forced" root filters as later described. Weighted median filters for noise reduction are well documented in specialist literature. An example is now outlined.
An ordinal filter is characterised by the number of sample values stored within the window. Then one of the values is selected for output. In the case of the median this is the middle ranked value, but other ranks (including maximum and minimum) can be selected. In one implementation of a weighted ordinal filter, multiple copies of each sample value are stored in the window and the rank selected as hitherto mentioned. Normally, but not essentially, the values in the centre of the window are given more weight than those at the edges and the median of the total number of samples is taken. For example, typical weights are: 1,1,2,5,2,1,1 in which case the 7th value in the sorted set is taken as the median. In one implementation of this circuit, the weights represent the number of copies of each sample input that are stored within the weighted median filter. This can be understood from FIG. 1 of the accompanying drawings, wherein SH1.1i,SH1.2i,SH1.3i are sample and hold amplifiers that store 3 samples input to stage 1 of the overall filter. These represent the input window to stage 1 of the datasieve. By connecting SH1.1i to SH1.1 one copy is included in the sort. By connecting SH1.2i to SH1.2, SH1.3 and SH1.4 three copies are included in the sort. Likewise SH1.3i is connected to SH1.5. This is not the only method for implementing a weighted median filter that has been documented in the specialist literature for noise reduction purposes.
Another aspect of the present invention lies in the incorporation of a series of weighted ordinal filters in a datasieve, for example for signal analysis, pattern recognition, noise reduction and data compression. A further aspect of the invention lies in a method for forcing a median filter output at each stage to a median root that is similar to but not identical to, the output obtained by repeated median filtering.
The present invention also principally concerns circuits for rapidly and efficiently implementing datasieves. In a simple circuit, such as that described in the abovementioned European Patent, there is an implication that at large R the number of values that need to be sorted will also be large. In practice this could limit the practicable use of datasieves both because of the complexity involved and the scale of the circuitry necessary to implement the datasieve and the time that such circuits would take to operate, especially if it is required to use datasieves for video image processing.
Hitherto datasieves have been implemented using standard median filters or standard morphological filters. The former involve a significant amount of sorting. On a computer this is time consuming so a number of attempts have been made to find hardware circuits to perform the median finding operation, see for example the Marconi MA7190 quoted in FIG. 4 and S D Richards "VLST Median filters" (IEEE ASSP vol.38: pp145-153). Although these designs fast, the size of window that can be implemented is still small by datasieve standards, for example, the MA7190 can only manage 15 samples. This is also true of standard morphological filters. Published work is confined to methods that involve small structuring elements (windows) by datasieve standards. It should be appreciated that it is not until a datasieve structure is used that there is any pressure to use large windows or structuring elements. It is only since the recent development of the datasieve, with its improved properties, that the need has arisen.
Yet a further aspect of the invention therefore aims to take advantage of the particular properties of the datasieve which make possible the implementation of simpler circuits, for example to enable complete processing to be achieved in a period of the order of seconds rather than the many hours necessary with existing proposals. This makes it practical to implement circuits that are more complex than those used for noise reduction.
Thus, the present invention also concerns signal analysis, and in particular analysis of image-containing signals. Existing systems will therefore now be briefly discussed.
Conventionally image analysis pattern recognition systems capable of handling multiple patterns at different scales concern two steps:
1. a re-representation of the optical image in a form suitable for classification, and
2. the step of classifying the object content of the re-represented data.
Often, linear multiscale transformers such as Gaussian filter banks are used in a data decomposition process in combination with edge detection and where appropriate thresholding.
The classifying step necessarily discards information when a decision is made such as "is this object an "X" type of object?".
However it has been found that conventional systems as outlined above are not capable of identifying similar complex objects of a given type from the field of view containing a multiplicity of data some relating to objects of the given type and others data relating to objects which are similar to but not identical to the given type of object, by matching or comparing the original image with a mask (itself derived from or accurately describing one of the complex objects within the original field), thresholding the result and attempting to identify and extract only data relating to objects having the same shape and pattern characteristics of the mask object (i.e. given type of object) by convolution with the mask. Conventional systems such as outlined have been found not to be selective enough in practice to exclude object data from objects which are very similar in frequency composition but not identical to the given type of object.
Signal decompositions can be used for pattern recognition in two distinct ways.
In one method signal decompositions provide multiscale smoothing prior to edge detection; this is beneficial for extracting only the significant edges from a noisy image. Many pattern recognition schemes use edge detection as a pre-processing step before classification. The datasieve provides good localisation of edges even in impulsive noise, which is desirable for robust pattern recognition.
An alternative method is to use a matching process, such as cross-correlation, to identify a target pattern within a noisy signal. The later described examples (FIGS. 9A, 9B, 10A and 10B) show that applying a matching process in the granularity domain obtained from the datasieve gives improved results compared with matching directly in the spatial (pixel) domain.
Alternatively, it may be stated that general pattern recognition systems, able to handle multiple patterns at different scales, should consist of two major steps, 1) the re-representation of the visual world in a form that is appropriate for 2) the classifier. This is illustrated in FIG. 8. For a system to be flexible, stage 200 should preserve all important information and therefore it should be possible to reconstruct the key features of the original signal 202 from the signal primitives 212. It is sometimes necessary to include extra processing stages 204,206 at this point. Linear multiscale transforms, such as Gaussian filter banks, are widely used for stage 200, because they allow reconstruction from the signal primitives.
Step 2, the classifier 209, necessarily discards information when a decision has to be made, for example, the binary decision "is this an "eye" or not?". Only one threshold stage 208 may be necessary, but usually this is not enough. For example, FIG. 9A and 9B show that a classical matched filter cannot discriminate the right eyes from all the surroundings and other features, e.g. sideburn/ears appear to be eyes when the original image (FIG. 9A) is cross-correlated with the mask (centre-most eye), the result is thresholded and the eyes revealed by convolution with the mask (FIG. 9B).
It is an object of the present invention in still another aspect to provide an improved image analysis system capable of reliably selecting objects having a particular shape and pattern (the target) from a field containing a plurality of such objects, in addition to many other objects some of which have very similar characteristics to those of the mask (target) object.
It is also an object of the invention, in yet another aspect, to provide a system for compressing image data without loss of the data relating to the significant elements making up the image.